class Node<T> {
  value: T;
  next: Node<T> | null = null;
  constructor(value: T) {
    this.value = value;
  }
}

class LinkedList<T> {
  private head: Node<T> | null = null;
  private size: number = 0;

  get length(): number {
    return this.size;
  }

  isEmpty(): boolean {
    return this.length === 0;
  }

  append(element: T) {
    const node = new Node(element);
    if (this.length === 0) {
      this.head = node;
    } else {
      let current = this.head!;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }

  insert(position: number, element: T): Node<T> | undefined {
    if (position >= 0 && position <= this.length) {
      const node = new Node(element);
      if (position === 0) {
        node.next = this.head;
        this.head = node;
      } else {
        const previous = this.getData(position - 1)!;
        const current = previous.next;
        previous.next = node;
        node.next = current;
      }
      this.size++;
      return node;
    }
    return undefined;
  }

  getData(position: number): Node<T> | undefined {
    if (position >= 0 && position < this.length) {
      let current = this.head!;
      for (let i = 0; i < position && current; i++) {
        current = current.next!;
      }
      return current;
    }
    return undefined;
  }

  indexOf(element: T): number {
    let current = this.head;
    for (let i = 0; i < this.size && current; i++) {
      if (current.value === element) {
        return i;
      }
      current = current.next;
    }
    return -1;
  }

  update(position: number, element: T): Node<T> | undefined {
    if (position >= 0 && position < this.length) {
      const current = this.getData(position)!;
      current.value = element;
      return current;
    }

    return undefined;
  }

  removeAt(position: number): Node<T> | undefined {
    if (position >= 0 && position < this.length) {
      let current = this.head!;
      if (position === 0) {
        this.head = current?.next;
      } else {
        const previous = this.getData(position - 1)!;
        current = previous?.next!;
        previous.next = current.next;
      }
      this.size--;
      return current;
    }
    return undefined;
  }

  remove(element: T): Node<T> | undefined {
    const index = this.indexOf(element);
    if (index !== -1) {
      return this.removeAt(index);
    }
  }

  toString(): string {
    let current = this.head;
    let result = "";

    // 遍历所有的节点，拼接为字符串，直到节点为 null
    while (current) {
      result += current.value + " ";
      current = current.next;
    }

    return result;
  }

  traverse(): string {
    const values: T[] = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }

    return values.join("-> ");
  }
}

export {};
